#include <stdio.h>
#include <stdlib.h>

typedef struct node Node, *NodePtr;
typedef struct linkedList LinkedList, *LinkedListPtr;

// 定义链表节点结构
typedef struct node {
    int data;
    NodePtr next;
} Node, *NodePtr;

typedef struct linkedList {
    int length;
    NodePtr head;
} LinkedList, *LinkedListPtr;

// 初始化链表
void initializeLinkedList (LinkedListPtr list) {
    printf("init ...\n");
    list->length =  0;
    list->head = NULL;
}

// 插入节点到链表头部，头插法
void insertNodeAtBeginning (LinkedListPtr list, int value) {
    // 节点开辟内存
    NodePtr newNode = (NodePtr) malloc(sizeof(Node));

    if (!newNode) {
        printf("Memory allocation failed...\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;
    newNode->next = list->head;
    list->length++;
    list->head = newNode;
}

// ***删除节点
void deleteNode(LinkedListPtr list, int value) {
    NodePtr current = list->head;
    NodePtr prev = NULL;

    while (current != NULL && current->data != value)
    {
        prev = current;
        current = current->next;
    }

    // 没有找到需要删除的节点
    if (current == NULL)
    {
        printf("Node with value %d not found ...\n", value);
        return;
    }

    // **判断是否为头结点
    if (prev == NULL)
    {
        // 删除的是头结点
        list->head = current->next;
        list->length--;
    } else {
        // 将前一个节点的next指向要删除节点的下一个节点
        prev->next = current->next;
        list->length--;
    }
    
    // 释放当前节点内存
    free(current);
}

// ***插入节点到指定位置
void insertNodeAtPosition (LinkedListPtr list, int value, int position) {
    if (position < 0) {
        printf("Invalid position ... \n");
        return;
    }

    NodePtr newNode = (NodePtr) malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed ...\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;

    if (position == 0)
    {
        // **插入第一个位置
        newNode->next = list->head;
        list->head = newNode;
        list->length++;
    } else {
        NodePtr current = list->head;
        // **找到第position前一个位置
        for (int i = 0; i < position - 1 && current != NULL; i++)
        {
            current = current->next;
        }

        // 如果current为空，则超出链表长度，插入失败，释放申请的节点内存
        if (current == NULL)
        {
            printf("Invalid position ...\n");
            free(newNode);
            return;
        }
        
        newNode->next = current->next;
        current->next = newNode;
        list->length++;
        
    } // if else end
    
}

// 打印链表中所有节点
void printLinkedList(LinkedListPtr list) {
    // 临时节点
    NodePtr current = list->head;

    printf("List length is: %d ...\n", list->length);
    printf("List: ");

    while (current) {
        printf("%d -> ", current->data);
        current = current->next;
    }

    printf("NULL \n");
}

// 在链表中查找指定值的节点
NodePtr searchNode(LinkedListPtr list, int value) {
    NodePtr current = list->head;

    while (current)
    {
        if (current->data == value) {
            // 找到目标节点并返回
            return current;
        }
        current = current->next;
    }

    // 没有找到节点返回空
    return NULL;
}

// 释放链表内存
void freeLinkedList(LinkedListPtr list) {
    printf("free ...\n");
    NodePtr current = list->head;
    NodePtr next;

    while (current)
    {
        next = current->next;
        free(current);
        current = next;
    }

    list->length = 0;
    list->head = NULL;
    
}


// 测试链表
void test() {
    printf("test LinkedList start... \n");
    // LinkedListPtr list;
    LinkedList list;

    initializeLinkedList(&list);

    // 1、插入节点到链表头部
    insertNodeAtBeginning(&list, 30);
    insertNodeAtBeginning(&list, 20);
    insertNodeAtBeginning(&list, 10);

    // 打印链表
    printLinkedList(&list);

    // 2、查找结点
    int searchValue = 20;
    NodePtr searchResult= searchNode(&list, searchValue);

    if (searchResult != NULL)
    {
        printf("Node with value %d found in the list ...\n", searchValue);
    } else {
        printf("Node with value %d not found in the list ...\n", searchValue);
    }

    // 3、删除节点
    int deleteValue = 20;
    deleteNode(&list, deleteValue);

    printLinkedList(&list);

    // 4、插入节点到指定位置
    int insertValue = 25;
    int insertPosition = 1;
    insertNodeAtPosition(&list, insertValue, insertPosition);

    printLinkedList(&list);

    freeLinkedList(&list);    

    printf("test LinkedList end ...\n");
}


int main() {

    printf("main ...");
    test();


    return 0;
}